#include <iostream>
#include <fstream>
#include <string>
#include <time.h>
#include <sys/time.h>
#include "Mochila.h"

using namespace std;

/************ FUNCIONES FICHEROS ****************************************
**Genera una Instancia del problema de la mochila y lo guarda en fs*/
void Mochila::generaInstancia(ofstream &fs){
   int n,pesoTotal=0,P;
   n = (rand()%MAX_OBJETOS)+1; //objetos:4-20 
   n = (n<4)?4:n;
   fs<<n<< endl; 
   for (int i = 0; i < n;i++){
      int p = (rand()%MAX_PESO)+1; //peso:1-100 
      int v = (rand()%MAX_PESO)+1; //valor:1-100 
      fs <<p<<" "<<v<< endl; 
      pesoTotal+=p;
   }
   P=(rand()%((int)(pesoTotal*0.6))+(pesoTotal/4));
   cout<<"Peso Total:"<<pesoTotal<<endl;
   fs<<P<< endl;
}

void Mochila::generaInstancia(ofstream &fs,int MAX){
   int n,pesoTotal=0,P;
   n = MAX; //objetos:4-20 
   n = (n<4)?4:n;
   fs<<n<< endl; 
   for (int i = 0; i < n;i++){
      int p = (rand()%MAX_PESO)+1; //peso:1-100 
      int v = (rand()%MAX_PESO)+1; //valor:1-100 
      fs <<p<<" "<<v<< endl; 
      pesoTotal+=p;
   }
   P=(rand()%((int)(pesoTotal*0.6))+(pesoTotal/4));
   cout<<"Peso Total:"<<pesoTotal<<endl;
   fs<<P<< endl;
}

void Mochila::generaInstanciaDirecta(int MAX){
   objetos.clear();
   int pesoTotal=0;
   n_objetos = MAX; //objetos:4-20 
   n_objetos = (n_objetos<4)?4:n_objetos;
   //fs<<n<< endl; 
   for (int i = 0; i < n_objetos;i++){
      int p = (rand()%MAX_PESO)+1; //peso:1-100 
      int v = (rand()%MAX_PESO)+1; //valor:1-100 
      //fs <<p<<" "<<v<< endl;
      Elemento el(p,v);
      objetos.push_back(el);
      pesoTotal+=p;
   }
   _P = (rand()%((int)(pesoTotal*0.6))+(pesoTotal/4));
   cout<<"Se han cargado "<<MAX<<" objetos con un peso total:"<<pesoTotal<<endl;
   cout<<"PESO MAXIMO MOCHILA:"<<_P<<endl;
   //fs<<P<< endl;
}

void Mochila::inicializa(){
   //P(0);
   pesoTotal(0);
   valorTotal(0);
   objetos_mochila = vector<bool>(objetos.size(),false);
   //n_objetos = 0;
}

void Mochila::cargaInstancia(ifstream &fs){
   inicializa();
   fs>>n_objetos;
   for (int i = 0; i < n_objetos;i++){
      int peso,valor;
      fs>>peso;
      fs>>valor;
      Elemento el(peso,valor);
      objetos.push_back(el);
   }
   fs>>_P;
  // muestraObjetos();
}

void Mochila::cargaFichero(string nombre){
   cout<<nombre<<endl;
   ifstream fsin(string(nombre).c_str(),ios::in);
   cargaInstancia(fsin);
   fsin.close();
}


/**************************** Auxiliares ************************************/

void Mochila::muestraObjetos(){
   if (P()>0){
      cout<<"*****************************************************"<<endl;
      cout<<" PESO MOCHILA: "<<P()<<endl;
      for (int i = 0; i < objetos.size();i++){
         cout<<"peso: "<<objetos[i].peso()<<" valor:"<<objetos[i].valor()<<endl;
      }
      cout<<"*****************************************************"<<endl;
   }
   else
      cout<<"¡¡¡¡¡¡¡¡¡Debe cargar una Instancia primero!!!!!!!!"<<endl;
}

void Mochila::objetosMochila(){
   for (int i = 0; i < objetos_mochila.size();i++){
      if (objetos_mochila[i])
         cout<<"Cogemos peso: "<<objetos[i].peso()<<" con valor: "<<objetos[i].valor()<<endl;
   }
}

/************************ ordenacion ***************************************/
void Mochila::ordenaPesos(){
   Elemento aux;
   for(int i=0;i<objetos.size()-1;i++) {
      for(int j=i+1;j<objetos.size();j++) {
         if (objetos[i].peso()>objetos[j].peso())
         {
            aux=objetos[i];
            objetos[i]=objetos[j];
            objetos[j]=aux;
         }
      }
   }
}

void Mochila::ordenaValor(){
   Elemento aux;
   for(int i=0;i<objetos.size()-1;i++) {
      for(int j=i+1;j<objetos.size();j++) {
         if (objetos[i].valor()<objetos[j].valor())
         {
            aux=objetos[i];
            objetos[i]=objetos[j];
            objetos[j]=aux;
         }
      }
   }
}

void Mochila::ordenaValorPeso(){
   Elemento aux;
   for(int i=0;i<objetos.size()-1;i++) {
      for(int j=i+1;j<objetos.size();j++) {
         if (((double)objetos[i].valor()/objetos[i].peso())<((double)objetos[j].valor()/objetos[j].peso()))
         {
            aux=objetos[i];
            objetos[i]=objetos[j];
            objetos[j]=aux;
         }
      }
   }
}

/*************************** heuristicas ***************************************/
void Mochila::heuristica1(){
   inicializa();
   for (int i = 0; i < objetos.size();i++){
      if ((_pesoTotal+objetos[i].peso()) < P()){
         objetos_mochila[i] = true;
         _pesoTotal += objetos[i].peso();
         _valorTotal += objetos[i].valor();
      }
      else
         break;
   }
}

double timeval_diff(struct timeval *a, struct timeval *b)
{
  return
    (double)(a->tv_sec + (double)a->tv_usec/1000000) -
    (double)(b->tv_sec + (double)b->tv_usec/1000000);
}

void Mochila::heuristicaValor(){
   inicializa();
   struct timeval ts1,ts2;
   double secs;

   gettimeofday(&ts1,NULL);
   if (objetos.size()>2){
      ordenaValor();
      heuristica1();
      gettimeofday(&ts2,NULL);
      secs = timeval_diff(&ts2,&ts1);
      cout<<" TIEMPO: "<<secs<<endl;
      cout<<" Valor: "<<_valorTotal<<" Peso: "<<_pesoTotal<<endl;
   }
   else
      cout<<"Error. No hay una instancia cargada"<<endl;
}

void Mochila::heuristicaPeso(){
   inicializa();
   struct timeval ts1,ts2;
   double secs;
   if (objetos.size()>2){
      gettimeofday(&ts1,NULL);
      ordenaPesos();
      heuristica1();
      gettimeofday(&ts2,NULL);
      secs = timeval_diff(&ts2,&ts1);
      cout<<" TIEMPO: "<<secs<<endl;
      cout<<" Valor: "<<_valorTotal<<" Peso: "<<_pesoTotal<<endl;
   }
   else
      cout<<"Error. No hay una instancia cargada"<<endl;
}

void Mochila::heuristicaValorPeso(){
   struct timeval ts1,ts2;
   double secs;
   if (objetos.size()>2){
      gettimeofday(&ts1,NULL);
      ordenaValorPeso();
      heuristica1();
      gettimeofday(&ts2,NULL);
      secs = timeval_diff(&ts2,&ts1);
      cout<<" TIEMPO: "<<secs<<endl;
      cout<<" Valor: "<<_valorTotal<<" Peso: "<<_pesoTotal<<endl;
   }
   else
      cout<<"Error. No hay una instancia cargada"<<endl;
}

/*************************** Exacto ***************************************/
void Mochila::exacto(){
   int i = 0,max=0;
   inicializa();
   vector<bool> X(objetos.size(),false);
   struct timeval ts1,ts2;
   double secs;
   gettimeofday(&ts1,NULL);

   back(X,i,max); //algoritmo Exacto
   //cout<<" valor conseguido: "<<max<<endl;
   _valorTotal = valor_acumulado(objetos_mochila,objetos_mochila.size()-1);
   _pesoTotal = peso_acumulado(objetos_mochila);
   gettimeofday(&ts2,NULL);
   secs = timeval_diff(&ts2,&ts1);
   cout<<" TIEMPO: "<<secs<<endl;
   cout<<" valor: "<<valor_acumulado(objetos_mochila,objetos_mochila.size()-1)<<" peso: "<<peso_acumulado(objetos_mochila)<<endl;
}

void Mochila::exactoPoda(){
   int i = 0,max=0;
   inicializa();
   vector<bool> X(objetos.size(),false);
   struct timeval ts1,ts2;
   double secs;
   gettimeofday(&ts1,NULL);

   ordenaValorPeso(); //ordenamos por Valor/Peso
   backPoda(X,i,max); //algoritmo Exacto
   cout<<" valor conseguido: "<<max<<endl;
   _valorTotal = valor_acumulado(objetos_mochila,objetos_mochila.size()-1);
   _pesoTotal = peso_acumulado(objetos_mochila);
   gettimeofday(&ts2,NULL);
   secs = timeval_diff(&ts2,&ts1);
   cout<<" TIEMPO: "<<secs<<endl;
   cout<<" valor: "<<valor_acumulado(objetos_mochila,objetos_mochila.size()-1)<<" peso: "<<peso_acumulado(objetos_mochila)<<endl;
}

bool Mochila::sol_factible(vector<bool> X,int k){
   int peso = 0;
   for (int i = 0; i <= k;i++){
      if (X[i] == true)
         peso += objetos[i].peso();
   }
   if (peso <= P())
      return true;
   else
      return false;
}

int Mochila::valor_acumulado(vector<bool> X,int k){
   int valor = 0;
   for (int i = 0; i <= k;i++){
      if (X[i] == true)
         valor += objetos[i].valor();
   }
   return valor;
}

int Mochila::peso_acumulado(vector<bool> X){
   int peso = 0;
   for (int i = 0; i < X.size();i++){
      if (X[i] == true)
         peso += objetos[i].peso();
   }
   return peso;
}

void Mochila::back(vector<bool> &X, int k, int &max_valor){
   for (int i = false; i <= true;i++){
      X[k] = i;
      if (sol_factible(X,k)) {
         if (k == X.size()-1) { //solucion completa
            int aux = valor_acumulado(X,k);
            if (aux > max_valor){
               max_valor = aux;
               objetos_mochila = X;
            }
         }
         else
            back(X,k+1,max_valor);
      }
   }
}

int Mochila::cota(vector<bool> &X, int k){
   int aux,aux2,aux3;
   for (int i = 0; i <= k;i++){
      aux += objetos[i].peso()*X[i];
      aux3 += objetos[i].valor()*X[i];
   }
   if ((k+1)>=objetos.size())
      k=k-1;
   aux2=(int)((P()-aux)/objetos[k+1].peso());
   aux2 = aux3+aux2*objetos[k+1].valor();
   return (aux2);
}

void Mochila::backPoda(vector<bool> &X, int k, int &max_valor){
   for (int i = false; i <= true;i++){
      X[k] = i;
      if (sol_factible(X,k) && (cota(X,k) > max_valor)) {
         if (k == X.size()-1) { //solucion completa
            int aux = valor_acumulado(X,k);
            if (aux > max_valor){
               max_valor = aux;
               objetos_mochila = X;
            }
         }
         else
            backPoda(X,k+1,max_valor);
      }
   }
}
